#include <vector>
#include <iostream>

namespace S1 {
    class Solution {
    public:
        // 1,2,3,0,0,0   3   [2,5,6]  3
        void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
            int k = m + n;
            std::vector<int> copy_nums(k, 0);

            if (n == 0) {
                for (auto& num : nums1) {
                    copy_nums.push_back(num);
                    std::cout << num << ",";
                }
                std::cout << std::endl;
                return;
            }

            int i = 0, j = 0, idx = 0;
            while(i < m) {
                if (nums1[i] < nums2[j]) {
                        copy_nums[idx] = nums1[i];
                        i++;
                        idx++;
                } else {
                    while (j < n && nums2[j] <= nums1[i]) {
                        copy_nums[idx] = nums2[j];
                        j++;
                        idx++;
                    }
                }
            }

            while (j < n) {
                copy_nums[idx] = nums2[j];
                j++;
                idx++;
            }
            
            for (auto& num : copy_nums) {
                std::cout << num << ",";
            }
            std::cout << std::endl;
        }
    };
}



// 上面的解法没有理解到题目的点上,导致错误
// 暴力的解法应该是先合并两个数组，然后再排序就可以了
// 这里使用的是O(m+n)
namespace S2 {
    // 双指针 
    // 暴力解法没有考虑到 给过来的数组已经排好序了，为了利用这一性质，
    // 解法：
    // 将两个数组看作是一个队列， 每次从两个数组头部取出比较小的数字放到结果中
    class Solution {
    public:
        void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
            int p1 = 0, p2 = 0;
            std::vector<int> sorted(m + n, 0);
            int cur;
            while (p1 < m || p2 < n) {
                if (p1 == m) {
                    cur = nums2[p2++];
                } else if (p2 == n) {
                    cur = nums1[p1++];
                } else if (nums1[p1] < nums2[p2]) {
                    cur = nums1[p1++];
                } else {
                    cur = nums2[p2++];
                }
                sorted[p1 + p2 - 1] = cur;
            }

            for (int i = 0; i != m + n; ++i) {
                nums1[i] = sorted[i];
            }
        }
    };
}

namespace S3 {
    class Solution {
    public:
        // 在方法二中使用临时变量，是因为如果直接合并到数组nums1中， 可能会在取出之前被覆盖，
        // 如何避免覆盖nums1中的元素呢， nums1的后半部分是空的，可以直接覆盖而不会影响结果，因此可以指针设置为从后前遍历，每次取两者之中的较大者放到nums1的后面
        void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
            int i = m - 1; // nums1的有效元素的索引
            int j = n - 1; // nums2的末尾索引
            int k = m + n - 1;    // nums1的最终位置末尾索引

            // 从后往前比较并合并
            while (i >=0 && j >= 0)
            {
                if (nums1[i] > nums2[j]) {
                    nums1[k--] = nums1[i--];
                } else {
                    nums1[k--] = nums2[j--];
                }
            }

            while (j >= 0)
            {
                nums1[k--] = nums2[j--];
            }
        }    
    };
}

int main() {

    S2::Solution s;
    std::vector<int> nums1 = {1,2,3,0,0,0};
    std::vector<int> nums2 = {2,5,6};
    // std::vector<int> nums1 = {1};
    // std::vector<int> nums2 = {};
    s.merge(nums1, 3, nums2, 3);
    return 0;
}